исчисление естественного вывода, натуральная дедукция, общее название логических исчислений, введённых и изученных в 1934 немецким логиком Г. Генценом (и независимо польским логиком С. Яськовским) с целью формализации процесса логического вывода, как можно более точно воспроизводящей структуру обычных содержательных рассуждений, а также для решения ряда важных задач метаматематики (См. Метаматематика) (в том числе для доказательства непротиворечивости (См. Непротиворечивость) арифметики натуральных чисел). Основным объектом Н. и. можно считать отношение (формальной) выводимости, обозначаемое символом ⊢, обладающее, по определению, свойством А А (здесь А - произвольное высказывание, выраженное формулой Н. и.) и удовлетворяющее следующим "структурным" правилам вывода (См. Правило вывода) (здесь и в дальнейшем в записи правил под горизонтальной чертой помещается выводимость, получаемая в предположении, что дана выводимость, записанная над чертой; прописные латинские буквы обозначают произвольные формулы, а греческие буквы - последовательности формул):

(разрешение усилить посылки), (разрешение опускать одну из совпадающих посылок), (разрешение переставлять посылки). В различных формулировках Н. и. вид и число структурных правил различны; например, понимая под Д и Г не последовательности, а просто конечные множества (неупорядоченные) формул, можно обойтись без правил перестановки посылок; обычное соглашение, что каждый элемент входит в него лишь один раз, делает ненужным правило сокращения повторяющихся посылок, и т.п. Кроме того, в Н. и. входят логические правила вывода, регламентирующие процедуру введения и удаления (устранения, исключения) символов логических операций и описывающие (как и аксиомы "обычных" логических исчислений; см., например, Логика высказываний) свойства этих операций. Вот правила классического Н. и. высказываний:

Введение

(так называемая "теорема о дедукции", см. Дедукция)

(reductio ad absurdum, или приведение к нелепости, см. Доказательство от противного) Удаление

(так называемое доказательство разбором случаев)

(modus ponens, или схема заключения)

(так называемый закон снятия двойного отрицания). (В скобках указана Интерпретация некоторых правил в терминах традиционной логики; интерпретация остальных правил - та же, что у соответствующих аксиом обычного исчисления высказываний, перефразировками которых они являются.) Добавление к этому списку соответствующих правил введения и удаления для Кванторов приводит к Н. и. предикатов. Замена правила -удаления на так называемое правило слабого -удаления ("из противоречия следует любое высказывание", см. Противоречия принцип) приводит к интуиционистскому (конструктивному) Н. и. высказываний (а с подходящими изменениями в кванторных правилах - к интуиционистскому Н. и. предикатов; см. Математический интуиционизм, Конструктивное направление).

Доказательство в Н. и. - это, как обычно, вывод из пустого множества посылок. В формулировках Н. и., подобных приведённой, в которых нет аксиом (кроме, быть может, А А), источником получения "логических законов", выражаемых формулами, доказуемыми без привлечения каких бы то ни было гипотез (посылок), оказывается правило ⊃-введения. Гибкость аппарата Н. и., близость его к привычным формам содержательных рассуждений и простота получающихся выводов делают его удобным орудием логико-математического исследования. Н. и. полезно и в тех случаях, когда применяются другие системы логики: в качестве источника выводимых (дополнительных) правил вывода, применение которых также значительно упрощает логический аппарат, а также для получения эвристических (предварительных, подлежащих дальнейшему обоснованию) доводов, которые так или иначе должны предшествовать любому формальному доказательству (как источник доказываемых или опровергаемых гипотез).

Лит.: Клини С. К., Введение в метаматематику, пер. с англ., М., 1957, §§ 20, 23; Генцен Г., Исследования логических выводов, пер. с. нем., в кн.: Математическая теория логического вывода, М., 1967; Карри Х. Б., Основания математической логики, пер. с англ., М., 1969. См. также лит. при ст. Правило вывода.

Ю. А. Гастов.

основанный на чётко сформулированных правилах формальный аппарат оперирования со знаками определённого вида, позволяющий дать исчерпывающе точное описание некоторого класса задач, а для некоторых подклассов этого класса (лишь для наиболее простых И., совпадающих с ним) - и Алгоритмы решения. Примерами И. могут служить совокупность арифметических правил оперирования с цифрами (т. е. числовыми знаками), "буквенное" И. элементарной алгебры, дифференциальное И., интегральное И., вариационное И. и другие ветви математического анализа и теории функций. Несмотря на раннее происхождение, термин "И." употреблялся в математике до недавнего времени без строгого общего определения. С развитием математической логики возникла потребность в общей теории И. и в уточнении самого понятия "И.", которое подверглось более последовательной формализации. В большинстве случаев, однако, оказывается достаточным следующее (идущее от Д. Гильберта) представление об И. Рассматривается некоторый (вообще говоря, бесконечный, хотя и, быть может, задаваемый посредством конечного числа символов) алфавит, из элементов которого, именуемых буквами, с помощью четко сформулированных правил образования строятся формулы рассматриваемого И. (называемые также иногда словами, или выражениями). Некоторые из таких ("правильно построенных") формул объявляются аксиомами, а из них с помощью правил преобразования (или, иначе, правил вывода) "выводятся" новые формулы, называемые теоремами данного И. Иногда термин "И." относят лишь к "словарной" ("выразительной") части описанного построения, говоря, что присоединение к ней "дедуктивной" части (т. е. добавление к алфавиту и правилам образования аксиом и правил ввода) даёт формальную систему. Впрочем, эти термины часто считают синонимичными (и в качестве синонимов пользуются также терминами "логистическая система", "формализм", "формальная теория" и многими др.). Если такое неинтерпретированное ("бессмысленное") И. сопоставить с некоторой интерпретацией (См. Интерпретация) (или, как говорят, дополнить чисто синтаксические рассмотрения некоторой семантикой; см. Логическая семантика) то получают Формализованный язык. Представление содержательных логических (и логико-математических) теорий в виде формализованных языков есть характерная особенность математической логики (см. также Доказательство).

Лит.: Клини С. К., Введение в метаматематику, пер. с англ., М., 1957, § 14-20; Марков А. А., Теория алгорифмов, М.-Л., 1954 (Тр. Математического института им. В. А. Стеклова, т. 42); Карри Х. Б., Основания математической логики, пер. с англ., М., 1969, гл. 2; Математическая теория логического вывода, Сборник переводов, под ред. А. В. Идельсона, Г. Е. Минца, М., 1967; Логические и логико-математические исчисления, 1, Сб. работ, под ред. В. П. Оревкова, Л., 1968.

Ю. Л. Гастев.